#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=1e5+10,M=N*2;
int h[N],e[M],ne[M],w[N];
int n;
int d[N];
void dij(int s)
{
    priority_queue<PII>q;
    q.push({0,s});
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    while(q.size()){
	PII t=q.top();
	q.pop();
	int dis=t.x;
	int ver=t.y;
	for(int i=h[ver];~i;i=ne[i]){
	    int j=e[i];
	    if(d[j]>dis+w[i]){
		d[j]=dis+w[i];
		q.push({j,d[j]});
	    }
	}
    }
 
}
int main()
{
    return 0;
}
